package com.dyz.LeetCodeforSwordFingerOffer;

import java.util.Stack;

public class GetIntersectionNode52 {
    //思路：使用栈，先进后出
    private Stack<ListNode> stack1 = new Stack();
    private Stack<ListNode> stack2 = new Stack<>();
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //处理特殊值
        if(headA==null || headB ==null){return null;}
        ListNode h1 = headA;
        ListNode h2 = headB;
        ListNode res = null;
        while (h1!=null){
            stack1.push(h1);
            h1 = h1.next;
        }
        while (h2!=null){
            stack2.push(h2);
            h2 = h2.next;
        }
        while (!stack1.isEmpty() && !stack2.isEmpty()){
            ListNode n1 = stack1.pop();
            ListNode n2 = stack2.pop();
            if (n1 == n2){
                res = n1;
            }
        }
        return res;
    }

    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        ListNode node1 = headA;
        ListNode node2 = headB;
        while(node1 != node2) {
            node1 = (node1 != null) ? node1.next : headB; // 若遍历完链表 A则从链表 B开始继续走
            node2 = (node2 != null) ? node2.next : headA; // 若遍历完链表 B则从链表 A开始继续走
        }
        return node1; // 若有重合，最终一定会相遇，node1和 node2均指向公共节点，否则 node1和 node2均为空
    }
}
